package hashmap;

public class MyHashMap<K,V> {

    //定义的结点
    static class Node<K,V>{
        public K key;
        public V val;

        public Node<K,V> next;

        public Node(K key,V val) {
            this.key = key;
            this.val = val;
        }

    }


    public Node<K,V>[] array =  new Node[10];
    public int usedSize;//记录map中的结点个数，用于扩容

    public static final double  LOAD_FACTOR = 0.75; //扩容因子



    /**
     *  插入操作
     * @param key
     * @param val
     */
    public void push(K key,V val) {
        //1.找位置
        Node<K,V> node = new Node(key,val);
        int index = key.hashCode() % array.length;
        Node<K,V> cur = array[index];
        while (cur != null) {  //尾插
            if(cur.key.equals(key)) {//修改原本key的value
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        //不存在节点的情况
        node.next = array[index];
        array[index] = node;
        usedSize++;
        if(doLoadFactor() >= 0.75) reSize();
    }


    /**
     * 扩容  -- 重新哈希
     */
    private void reSize() {
        Node<K,V>[] newArray = new Node[array.length * 2];
        int len = newArray.length;
        for(int i=0;i<array.length;i++) { //遍历原始数组
            Node<K,V> cur = array[i];
            while (cur != null) { //遍历每一条链表
                Node<K,V> next = cur.next;
                int index = cur.key.hashCode() % len;
                //头插操作
                cur.next = newArray[index];
                newArray[index] = cur;
                cur = next;
            }
        }
        array = newArray;
    }

    /**
     * 是否需要扩容 -- 根据扩容因子
     * @return
     */
    private double doLoadFactor() {
        return usedSize*1.0 / array.length;
    }



    /**
     * 获取key对应的value
     * @param key
     * @return
     */
    public V get(K key) {
        int index = key.hashCode() % array.length;
        Node<K,V> cur = array[index];
        while (cur != null) {
            if(cur.key.equals(key)) return cur.val;
            cur = cur.next;
        }
        return null;
    }

    /**
     * 获取key对应的value，不存在返回指定值
     * @param key
     * @param value
     * @return
     */
    public V getOrDefault(K key,V value) {
        int index = key.hashCode() % array.length;
        Node<K,V> cur = array[index];
        while (cur != null) {
            if(cur.key.equals(key)) return cur.val;
            cur = cur.next;
        }
        return value;
    }

    /**
     * 移除key-value对应关系
     * @param key
     * @return
     */
    public Boolean remove(K key) {
        int index = key.hashCode() % array.length;
        Node<K,V> cur = array[index];
        if(cur == null) return false;
        //1.判断第一个
        if(cur.key.equals(key)) {
            array[index] = cur.next;
            usedSize--;
            return true;
        }
        //2.判断后续的结点
        Node<K,V> parent = cur;
        cur = cur.next;
        while (cur != null) {
            if(cur.key.equals(key)) {
                parent.next = cur.next;
                usedSize--;
                return true;
            }
            parent = cur;
            cur = cur.next;
        }
        return false;
    }

}
